package com.yequan.leetcode.stack.largestRectangleArea_84;

/**
 * //给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * //
 * // 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * //
 * //
 * //
 * //
 * //
 * // 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
 * //
 * //
 * //
 * //
 * //
 * // 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
 * //
 * //
 * //
 * // 示例:
 * //
 * // 输入: [2,1,5,6,2,3]
 * //输出: 10
 * // Related Topics 栈 数组
 *
 * @author : Administrator
 * @date : 2020/3/21
 */
public class LargestRectangleArea {

    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        LargestRectangleArea largestRectangleArea = new LargestRectangleArea();
        int maxArea = largestRectangleArea.largestRectangleArea1(heights);
        System.out.println(maxArea);
    }

    /**
     * 暴力法
     *
     * @param heights
     * @return
     */
    public int largestRectangleArea1(int[] heights) {
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            for (int j = i; j < heights.length; j++) {
                int minHeight = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) {
                    minHeight = Math.min(minHeight, heights[k]);
                }
                maxArea = Math.max(maxArea, minHeight * (j - i + 1));
            }
        }
        return maxArea;
    }

}
